贪心算法

发表于 | 分类于 | |

🤔

概念

  • 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的 算法 。比如在 旅行推销员问题 中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

  • 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

  • 贪心算法与 动态规划 的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
    贪心法可以解决一些 最优化 问题，如：求中的 最小生成树 、求 哈夫曼编码 ……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

思路

  1. 建立数学模型来描述问题。
  2. 把求解的问题分成若干个子问题。
  3. 对每一子问题求解，得到子问题的局部最优解。
  4. 把子问题的解局部最优解合成原来解问题的一个解。
  • 实现该算法的过程：
    从问题的某一初始解出发；while 能朝给定总目标前进一步 do ,求出可行解的一个解元素；最后，由所有解元素组合成问题的一个可行解。

案例

  1. 这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。
    可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    include<cstdio>
    #include<iostream> 
    #include<algorithm> 
    using namespace std;    
    int N;
    struct Act
    {
    	int start;
    	int end;
    }act[100010];

    bool cmp(Act a,Act b)  
    {  
        return a.end<b.end;  
    } 

    int greedy_activity_selector()  
    {  
    	int num=1,i=1;   
        for(int j=2;j<=N;j++)  
        {  
            if(act[j].start>=act[i].end)  
            {  
                i=j;  
                num++;  
            }  
        }  
        return num;
    }

    int main()  
    {  
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&N);
    		for(int i=1;i<=N;i++)
    		{
    			scanf("%lld %lld",&act[i].start,&act[i].end);
    		}
    		act[0].start=-1;
    		act[0].end=-1;
    	 	sort(act+1,act+N+1,cmp); 
        	int res=greedy_activity_selector();
    		cout<<res<<endl;  
    	}
    }

  2. 钱币找零问题
    这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=7; 
    int Count[N]={3,0,2,1,0,3,5};
    int Value[N]={1,2,5,10,20,50,100};
      
    int solve(int money) 
    {
    	int num=0;
    	for(int i=N-1;i>=0;i--) 
    	{
    		int c=min(money/Value[i],Count[i]);
    		money=money-c*Value[i];
    		num+=c;
    	}
    	if(money>0) num=-1;
    	return num;
    }
     
    int main() 
    {
    	int money;
    	cin>>money;
    	int res=solve(money);
    	if(res!=-1) cout<<res<<endl;
    	else cout<<"NO"<<endl;
    }

  3. 背包问题
    有一个背包，背包容量是M。有n个重量和价值分别为Wi和Vi的物品，物品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include<iostream>   
    using namespace std;   
    const int N=4;  
    void knapsack(float M,float v[],float w[],float x[]);  
      
    int main()  
    {  
        float M=50;
    	//背包所能容纳的重量   
        float w[]={0,10,30,20,5};
    	//每种物品的重量  
        float v[]={0,200,400,100,10};  
      	//每种物品的价值 
        float x[N+1]={0};  
        //记录结果的数组 
        knapsack(M,v,w,x);  
        cout<<"选择装下的物品比例："<<endl;  
        for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;  
    }  
      
    void knapsack(float M,float v[],float w[],float x[])  
    {  
        int i;  
        //物品整件被装下  
        for(i=1;i<=N;i++)
        {  
            if(w[i]>M) break;   
            x[i]=1;  
            M-=w[i];  
        }   
        //物品部分被装下  
        if(i<=N) x[i]=M/w[i];   
    }

  4. 多机调度问题
    N个作业组成的作业集，可由m台相同机器加工处理。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业；每个作业均可在任何一台机器上加工处理。这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。在下面的代码中没有讨论n和m的大小关系，把这两种情况合二为一了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include<iostream>  
    #include<algorithm>    
    using namespace std;  
    int speed[10010];  
    int mintime[110];  

    bool cmp( const int &x,const int &y)  
    {  
        return x>y;  
    }  

    int main()  
    {  
    	int n,m;         
    	memset(speed,0,sizeof(speed));  
     	memset(mintime,0,sizeof(mintime));  
      	cin>>n>>m;  
       	for(int i=0;i<n;++i) cin>>speed[i];  
        sort(speed,speed+n,cmp);  
        for(int i=0;i<n;++i)   
        { 
        	*min_element(mintime,mintime+m)+=speed[i];   
       	}   
        cout<<*max_element(mintime,mintime+m)<<endl; 
    }

  5. 小船过河问题
    POJ1700是一道经典的贪心算法例题。题目大意是只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式：
    1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2t[1]+t[n-1]；
    2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2    t[0]+t[n-2]+t[n-1]。
    算一下就知道，除此之外的其它情况用的时间一定更多。每次都运送耗时最长的两人而不影响其它人，问题具有贪心子结构的性质。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #include<iostream>
    #include<algorithm>
    using namespace std;

    int main()
    {
    	int a[1000],t,n,sum;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		sum=0;
            for(int i=0;i<n;i++) scanf("%d",&a[i]);
            while(n>3)
    		{
    			sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);
                n-=2;
            }
            if(n==3) sum+=a[0]+a[1]+a[2];
            else if(n==2) sum+=a[1];
            else sum+=a[0];
            printf("%d\n",sum);
    	}
    }

  6. 区间覆盖问题
    POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛，我们可以计算出一个雷达所在位置的区间。

    问题转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序，初始时需要一个点。如果两个区间相交而不重合，我们什么都不需要做；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct Point
    {
    	double x;
    	double y;
    }point[1000];

    int cmp(const void *a, const void *b)
    {
        return (*(Point *)a).x>(*(Point *)b).x?1:-1;
    }

    int main()
    {
    	int n,d;
    	int num=1;
    	while(cin>>n>>d)
    	{
    		int counting=1;
    		if(n==0&&d==0) break;
    		for(int i=0;i<n;i++)
    		{
    			int x,y;
    			cin>>x>>y;
    			if(y>d)
    			{
    				counting=-1;
    			}
    			double t=sqrt(d*d-y*y);
    			//转化为最少区间的问题 
    			point[i].x=x-t;
    			//区间左端点 
    			point[i].y=x+t;
    			//区间右端点 
    		}
    		if(counting!=-1)
    		{
    			qsort(point,n,sizeof(point[0]),cmp);
    			//按区间左端点排序 
    			double s=point[0].y;
    			//区间右端点 
    			for(int i=1;i<n;i++)
    			{
    				if(point[i].x>s)
    				//如果两个区间没有重合,增加雷达数目并更新右端点 
    				{
    					counting++;
    					s=point[i].y; 
    				}
    				else if(point[i].y<s)
    				//如果第二个区间被完全包含于第一个区间,更新右端点 
    				{
    					s=point[i].y;
    				}
    			}
    		}
    		cout<<"Case "<<num<<':'<<' '<<counting<<endl;
    		num++; 
    	}
    }

  7. Huffman编码
    这同样是《算法导论》上的例子。Huffman编码是广泛用于数据文件压缩的十分有效的编码方法。我们可以有多种方式表示文件中的信息，如果用01串表示字符，采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300000位；采用变长编码表示，给频率高的字符较短的编码，频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可见，变长码比定长码方案好，总码长减小约25%。

    对每一个字符规定一个01串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，这种编码称为前缀码。可能无前缀码是一个更好的名字，但是前缀码是一致认可的标准术语。编码的前缀性质可以使译码非常简单：例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。译码过程需要方便的取出编码的前缀，为此可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的路标。

    从上图可以看出，最优前缀编码码的二叉树总是一棵完全二叉树，而定长编码的二叉树不是一棵完全二叉树。 给定编码字符集C及频率分布f，C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)，dT(c)也是字符c的前缀码长。则平均码长定义为：

    使平均码长达到最小的前缀码编码方案称为C的最优前缀码。
    Huffman编码的构造方法：先合并最小频率的2个字符对应的子树，计算合并后的子树的频率；重新排序各个子树；对上述排序后的子树序列进行合并；重复上述过程，将全部结点合并成1棵完整的二叉树；对二叉树中的边赋予0、1，得到各字符的变长编码。

    POJ3253一道就是利用这一思想的典型例题。题目大意是有把一块无限长的木板锯成几块给定长度的小木板，每次锯都需要一定费用，费用就是当前锯的木板的长度。给定各个要求的小木板的长度以及小木板的个数，求最小的费用。以要求3块长度分别为5,8,5的木板为例：先从无限长的木板上锯下长度为21的木板，花费21；再从长度为21的木板上锯下长度为5的木板，花费5；再从长度为16的木板上锯下长度为8的木板，花费8；总花费=21+5+8=34。利用Huffman思想，要使总费用最小，那么每次只选取最小长度的两块木板相加，再把这些和累加到总费用中即可。为了提高效率，使用优先队列优化，并且还要注意使用long long int保存结果。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include<queue>
    #include<cstdio>
    #include<iostream>
    using namespace std;

    int main()
    {
        long long int sum;
        int i,n,t,a,b;
        while(~scanf("%d",&n))
        {
            priority_queue<int,vector<int>,greater<int> >q;
            for(i=0;i<n;i++)
            {
    			scanf("%d",&t);
    			q.push(t);
            }
            sum=0;
            if(q.size()==1)
            {
                a=q.top();
                sum+=a;
                q.pop();
            }
            while(q.size()>1)
            {
                a=q.top();
                q.pop();
                b=q.top();
                q.pop();
                t=a+b;
                sum+=t;
                q.push(t);
            }
            printf("%lld\n",sum);
        }
    }
宇 wechat
扫描二维码，订阅微信公众号